package array_linklist

import (
	"sort"
	"strings"
)

// 找出数组中重复的数字。
//
// https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/
type FindRepeatNumber struct{}

// solutionUseOrder 排序+遍历->找出重复
func (q FindRepeatNumber) solutionUseOrder(nums []int) int {
	sort.Ints(nums)
	for k := 0; k < len(nums)-1; k++ {
		if nums[k] == nums[k+1] {
			return nums[k]
		}
	}
	return -1
}

// solutionUseMap 遍历+map->找重
func (q FindRepeatNumber) solutionUseMap(nums []int) int {
	m := make(map[int]int)
	for k, v := range nums {
		if _, ok := m[v]; ok {
			return v
		}
		m[v] = k
	}
	return -1
}

// solutionInPlace 不使用额外空间解决方案
// 抽屉原理解法：按下标重新排列数组值->找出重复
func (q FindRepeatNumber) solutionInPlace(nums []int) int {
	for k := 0; k < len(nums); k++ {
		for nums[k] != k { // 处理数的交换
			// 退出条件：序号对应的值 等于 序号对应值作为序号所对应的值
			if nums[k] == nums[nums[k]] {
				return nums[k]
			}
			nums[nums[k]], nums[k] = nums[k], nums[nums[k]]
		}

	}
	return -1
}

/**
FindNumberIn2DArray 二维数组中的查找
https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/
*/
type FindNumberIn2DArray struct{}

// solutionFromRight 从右上角开始对比
func (q FindNumberIn2DArray) solutionFromRight(matrix [][]int, target int) bool {
	// 下面三个判断位置不要乱
	if matrix == nil || len(matrix) == 0 || len(matrix[0]) == 0 {
		return false
	}
	rows, cols := len(matrix), len(matrix[0])
	row, col := 0, cols-1
	for row < rows && col >= 0 {
		num := matrix[row][col]
		if target == num {
			return true
		} else if num > target {
			col--
		} else {
			row++
		}
	}
	return false
}

// solutionFromLeft 从左下角开始对比
// 不知道为啥跑出来就是要慢一些
func (q FindNumberIn2DArray) solutionFromLeft(matrix [][]int, target int) bool {
	if matrix == nil || len(matrix) == 0 || len(matrix[0]) == 0 {
		return false
	}
	rows, cols := len(matrix), len(matrix[0])
	row, col := rows-1, 0
	for row >= 0 && col < cols {
		num := matrix[row][col]
		if target == num {
			return true
		} else if num > target {
			row--
		} else {
			col++
		}
	}
	return false
}

// 替换空格
// 也算是数组类的问题吧
// https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/
type ReplaceSpace struct{}

// solutionUseLib 使用字符串操作函数
func (q ReplaceSpace) solutionUseLib(s string) string {
	return strings.ReplaceAll(s, " ", "%20")
}

// solutionUseArray 基于数组的操作
// 两者执行效率似乎差距不大。
// 理清题设，找出不用标准库也能实现的方法
func (q ReplaceSpace) solutionUseArray(s string) string {
	n := len(s) * 3
	arr := make([]byte, n) // 只能用切片。给好容量也差不多
	index := 0
	for _, v := range []byte(s) {
		if v == ' ' {
			arr[index] = '%'
			index++ // golang 自增运算只能作为语句，不能作为表达式
			arr[index] = '2'
			index++
			arr[index] = '0'
			index++
		} else {
			arr[index] = v
			index++
		}
	}
	return string(arr[:index])
}

// CountOneInBinary 二进制中1的个数
// 事实上，此题是说输入32位的二进制数，输出它的1的个数
// 此题在leetcode上GoLang解法运行有问题，不能正确地将二进制数传过来
// https://leetcode-cn.com/problems/er-jin-zhi-zhong-1de-ge-shu-lcof/
type CountOneInBinary struct{}

// solution1 解法1：循环和位移动
// 因为1&0 = 0 的，所以可以用1与输入 数的每位进行比较
func (c *CountOneInBinary) solution1(n int) int {
	bits, mask := 0, 1
	for i := 0; i < 32; i++ {
		if (n & mask) != 0 {
			bits++
		}
		mask <<= 1
	}
	return bits
}

// 技巧性太高。还没理解到。
func (c *CountOneInBinary) solution2(n int) int {
	sum := 0
	for n != 0 {
		sum++
		n &= (n - 1)
	}
	return sum
}

// MergeTwoArrs 合并排序的数组
// https://leetcode-cn.com/problems/sorted-merge-lcci/
type MergeTwoArrs struct{}

// 双指针法：正向循环
func (q *MergeTwoArrs) solution(A []int, m int, B []int, n int) {
	sorted := make([]int, m+n)
	pa, pb := 0, 0 // 为A B数组设定指针
	index := 0     // 计数君
	for pa < m || pb < n {
		if pa == m { // A数组到头的情况
			sorted[index] = B[pb]
			pb++
		} else if pb == n { // B数组到头的情况
			sorted[index] = A[pa]
			pa++
		} else if A[pa] >= B[pb] { // 两数组的数比较
			sorted[index] = B[pb]
			pb++
		} else {
			sorted[index] = A[pa]
			pa++
		}
		index++ // 计数君加1
	}

	A = append(A[:0], sorted...) // Go数组数据覆盖操作

}

// 双指针法：逆向循环
// A、B已排序，A有足够容纳B的空间；从后向前，从大到小必定比对完每个数且有序
// 对比上一种解法，少用一个辅助数组
func (q *MergeTwoArrs) solution2(A []int, m int, B []int, n int) {

	pa, pb := m-1, n-1       // 为A B数组设定指针
	index := m + n - 1       // 计数君
	for pa >= 0 || pb >= 0 { // 大于等于 这个条件得品，细品
		if pa == -1 { //品
			A[index] = B[pb]
			pb--
		} else if pb == -1 {
			A[index] = A[pa]
			pa--
		} else if A[pa] >= B[pb] {
			A[index] = A[pa]
			pa--
		} else {
			A[index] = B[pb]
			pb--
		}
		index--
	}
}
